
/**
 * 常用排序功能
 */


/**
 * 冒泡排序
 * 外层循环：控制遍历的次数。最多需要遍历 n-1 次，其中 n 是数组的长度。
 * 内层循环：在每次外层循环中，对数组进行遍历，比较相邻的元素，如果顺序错误则交换它们。
 * 优化：可以设置一个标志位，如果在某次内层循环中没有发生任何交换，说明数组已经排序完成，可以提前退出。
 * @param {*} arr 
 * @returns 
 */
export function bubbleSort(arr) {
    let len = arr.length;
    let swapped;
    for (let i = 0; i < len; i++) {
        swapped = false; // 标志位，记录当前遍历是否发生了交换
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        // 如果某次内层循环没有发生交换，说明数组已经有序，提前退出
        if (!swapped) {
            break;
        }
    }
    return arr;
}

/**
* 选择排序
* 外层循环：控制遍历的次数。最多需要遍历 n-1 次，其中 n 是数组的长度。
* 内层循环：在每次外层循环中，从未排序部分找到最小（或最大）元素的索引。
* 交换：将找到的最小（或最大）元素与未排序部分的第一个元素交换位置。
* 更新边界：每次外层循环结束后，未排序部分的边界向内收缩。
* @param {*} arr 
* @returns 
*/
export function selectionSort(arr) {
    let len = arr.length;
    let minIndex, temp;
    for (let i = 0; i < len - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

/**
* 插入排序：原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
* 外层循环：控制未排序部分的起始位置。从数组的第二个元素开始，因为第一个元素可以认为已经被排序。
* 内层循环：在未排序部分中，从当前元素的前一个位置开始向前扫描，寻找当前元素应该插入的位置。
* 元素后移：如果当前扫描的元素大于待插入元素，则将该元素向后移动一位，为待插入元素腾出空间。
* 插入元素：当找到待插入元素的位置后，将其插入到该位置。
* 重复：重复步骤2-4，直到未排序部分为空。
* @param {*} arr 
* @returns 
*/
export function insertionSort(arr) {
    let n = arr.length;
    // 外层循环，控制未排序部分的起始位置
    for (let i = 1; i < n; i++) {
        let key = arr[i]; // 待插入元素
        let j = i - 1;
        
        // 内层循环，从未排序部分向前扫描，寻找插入位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // 元素后移            
            j--;
        }
        
        // 插入元素到正确位置
        arr[j + 1] = key;
    }
    
    return arr;
}

/**
* 归并排序:将一个列表分成小的子列表，然后递归地排序每个子列表，最后将已排序的子列表合并成一个完整的排序列表。
* @param {*} arr 
* @returns 
*/
function merge(left, right) {
    let result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    // 比较两个子数组的元素，并按顺序放入结果数组
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    // 将剩余的元素（如果有）添加到结果数组
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
export function mergeSort(arr) {
    // 如果数组长度小于等于1，直接返回数组
    if (arr.length < 2) {
        return arr;
    }
    // 找到数组的中间索引
    let middle = Math.floor(arr.length / 2);
    // 递归地将数组分成两半并排序
    let left = arr.slice(0, middle);
    let right = arr.slice(middle);
    // 合并两个排序后的子数组
    return merge(mergeSort(left), mergeSort(right));
}

/**
* 快速排序：策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。
* @param {*} arr 
* @returns 
*/
export function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let pivotIndex = Math.floor(arr.length / 2);
    let pivot = arr.splice(pivotIndex, 1)[0];
    let left = [];
    let right = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat([pivot], quickSort(right));
}

/**
* 堆排序
* 将无序数组看作一个完全二叉树，从最后一个非叶子节点开始，自底向上调整堆，使其满足最大堆性质。
* 将堆顶元素（最大值）与末尾元素交换，缩小堆的范围（排除已排序的末尾元素）。
* 重新调整堆，使其继续满足最大堆性质。
* 重复上述步骤，直到堆的范围缩小到只剩一个元素。
* @param {*} arr 
* @returns 
*/ 
export function heapSort(arr) {
    let n = arr.length;
 
    // 构建最大堆
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
 
    // 一个个从堆顶取出元素，放到数组末尾（已排序部分），然后重新调整堆
    for (let i = n - 1; i > 0; i--) {
        // 交换当前堆顶（最大值）和数组末尾的元素
        let temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
 
        // 调整剩余部分为最大堆
        heapify(arr, i, 0); // 注意这里传递的堆大小是 i，根节点索引是 0
    }
 
    // 堆排序是原地排序，不需要返回值，排序后的数组就是 arr 本身
    return arr; // 虽然不需要，但为了符合一般函数习惯，可以返回 arr
}
function heapify(arr, n, i) {
    let largest = i; // 初始化最大值为根节点
    let left = 2 * i + 1; // 左子节点的索引
    let right = 2 * i + 2; // 右子节点的索引
 
    // 如果左子节点存在且大于根节点
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
 
    // 如果右子节点存在且大于当前最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
 
    // 如果最大值不是根节点
    if (largest !== i) {
        // 交换
        let temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest); // 递归堆化受影响的子树
    }
}
/**
 * 顺序查找：它从数据结构的第一个元素开始，依次比较每个元素，直到找到目标元素或者查找完所有元素为止。顺序查找适用于数据量较小或数据无序的情况。
 * @param {*} arr 
 * @param {*} target 
 * @returns 
 */
function linearSearch(arr, target) {
    // arr 是要查找的数组
    // target 是要查找的目标元素
    
    // 遍历数组中的每一个元素
    for (let i = 0; i < arr.length; i++) {
        // 如果当前元素等于目标元素，则返回当前元素的索引
        if (arr[i] === target) {
            return i;
        }
    }
    
    // 如果遍历完整个数组都没有找到目标元素，则返回 -1
    return -1;
}

/**
 * 二分查找（Binary Search）:是一种高效的查找算法，前提是数组或列表必须是有序的。
 * 它的基本思想是：通过逐步将查找范围减半来定位目标值。如果目标值小于中间元素，则在左半部分继续查找；
 * 如果目标值大于中间元素，则在右半部分继续查找。这个过程一直持续到找到目标值或者查找范围为空。
 * @param {*} arr 
 * @param {*} target 
 * @returns 
 */
function binarySearch(arr, target) {
    // arr 是要查找的有序数组
    // target 是要查找的目标元素
    
    let left = 0; // 左边界
    let right = arr.length - 1; // 右边界
    
    while (left <= right) {
        // 计算中间元素的索引，注意防止整数溢出
        let mid = Math.floor((left + right) / 2);
        
        // 检查中间元素是否是目标元素
        if (arr[mid] === target) {
            return mid; // 找到目标元素，返回其索引
        }
        
        // 如果目标元素大于中间元素，则忽略左半部分
        if (arr[mid] < target) {
            left = mid + 1;
        } else { // 如果目标元素小于中间元素，则忽略右半部分
            right = mid - 1;
        }
    }
    
    // 如果退出循环，说明目标元素不在数组中
    return -1;
}

/**
 * 插值查找（Interpolation Search）是二分查找的一种改进，它利用了数组中值的分布信息来预测目标值可能的位置，从而减少了比较次数。
 * 插值查找适用于数组中元素值分布均匀的情况。其基本思想是根据数组的大小和最小、最大值来估计目标值的位置，然后直接跳转到那个位置进行比较，而不是像二分查找那样总是跳转到中间位置。
 * @param {*} arr 
 * @param {*} target 
 * @returns 
 */

function interpolationSearch(arr, target) {
    // arr 是要查找的有序数组
    // target 是要查找的目标元素
    
    let left = 0; // 左边界
    let right = arr.length - 1; // 右边界
    
    while (left <= right && target >= arr[left] && target <= arr[right]) {
        // 如果目标值在数组范围之外，则退出循环
        
        // 使用插值公式计算目标值的估计位置
        let pos = left + ((right - left) / (arr[right] - arr[left])) * (target - arr[left]);
        
        // 检查估计位置的值
        if (arr[Math.floor(pos)] === target) {
            return Math.floor(pos); // 找到目标元素，返回其索引
        }
        
        // 如果目标值大于估计位置的值，则忽略左半部分（调整左边界）
        if (arr[Math.floor(pos)] < target) {
            left = Math.floor(pos) + 1;
        } else { // 如果目标值小于估计位置的值，则忽略右半部分（调整右边界）
            right = Math.floor(pos) - 1;
        }
    }
    
    // 如果退出循环，说明目标元素不在数组中
    return -1;
}
